home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / m68k / cc68k.arc / OPTIMIZE.C < prev    next >
C/C++ Source or Header  |  1986-10-26  |  15KB  |  392 lines
  1. #include        "stdio.h"
  2. #include        "c.h"
  3. #include        "expr.h"
  4. #include        "gen.h"
  5. #include        "cglbdec.h"
  6.  
  7. /*
  8.  *    68000 C compiler
  9.  *
  10.  *    Copyright 1984, 1985, 1986 Matthew Brandt.
  11.  *  all commercial rights reserved.
  12.  *
  13.  *    This compiler is intended as an instructive tool for personal use. Any
  14.  *    use for profit without the written consent of the author is prohibited.
  15.  *
  16.  *    This compiler may be distributed freely for non-commercial use as long
  17.  *    as this notice stays intact. Please forward any enhancements or question
  18. s
  19.  *    to:
  20.  *
  21.  *        Matthew Brandt
  22.  *        Box 920337
  23.  *        Norcross, Ga 30092
  24.  */
  25.  
  26.  dooper(node)
  27. /*
  28.  *      dooper will execute a constant operation in a node and
  29.  *      modify the node to be the result of the operation.
  30.  */
  31. struct enode    **node;
  32. {       struct enode    *ep;
  33.         ep = *node;
  34.         switch( ep->nodetype ) {
  35.                 case en_add:
  36.                         ep->nodetype = en_icon;
  37.                         ep->v.i = ep->v.p[0]->v.i + ep->v.p[1]->v.i;
  38.                         break;
  39.                 case en_sub:
  40.                         ep->nodetype = en_icon;
  41.                         ep->v.i = ep->v.p[0]->v.i - ep->v.p[1]->v.i;
  42.                         break;
  43.                 case en_mul:
  44.                         ep->nodetype = en_icon;
  45.                         ep->v.i = ep->v.p[0]->v.i * ep->v.p[1]->v.i;
  46.                         break;
  47.                 case en_div:
  48.                         ep->nodetype = en_icon;
  49.                         ep->v.i = ep->v.p[0]->v.i / ep->v.p[1]->v.i;
  50.                         break;
  51.                 case en_lsh:
  52.                         ep->nodetype = en_icon;
  53.                         ep->v.i = ep->v.p[0]->v.i << ep->v.p[1]->v.i;
  54.                         break;
  55.                 case en_rsh:
  56.                         ep->nodetype = en_icon;
  57.                         ep->v.i = ep->v.p[0]->v.i >> ep->v.p[1]->v.i;
  58.                         break;
  59.                 case en_and:
  60.                         ep->nodetype = en_icon;
  61.                         ep->v.i = ep->v.p[0]->v.i & ep->v.p[1]->v.i;
  62.                         break;
  63.                 case en_or:
  64.                         ep->nodetype = en_icon;
  65.                         ep->v.i = ep->v.p[0]->v.i | ep->v.p[1]->v.i;
  66.                         break;
  67.                 case en_xor:
  68.                         ep->nodetype = en_icon;
  69.                         ep->v.i = ep->v.p[0]->v.i ^ ep->v.p[1]->v.i;
  70.                         break;
  71.                 }
  72. }
  73.  
  74. int     pwrof2(i)
  75. /*
  76.  *      return which power of two i is or -1.
  77.  */
  78. int     i;
  79. {       int     p, q;
  80.         q = 2;
  81.         p = 1;
  82.         while( q > 0 )
  83.                 {
  84.                 if( q == i )
  85.                         return p;
  86.                 q <<= 1;
  87.                 ++p;
  88.                 }
  89.         return -1;
  90. }
  91.  
  92. int     mod_mask(i)
  93. /*
  94.  *      make a mod mask for a power of two.
  95.  */
  96. int     i;
  97. {       int     m;
  98.         m = 0;
  99.         while( i-- )
  100.                 m = (m << 1) | 1;
  101.         return m;
  102. }
  103.  
  104.  opt0(node)
  105. /*
  106.  *      opt0 - delete useless expressions and combine constants.
  107.  *
  108.  *      opt0 will delete expressions such as x + 0, x - 0, x * 0,
  109.  *      x * 1, 0 / x, x / 1, x mod 0, etc from the tree pointed to
  110.  *      by node and combine obvious constant operations. It cannot
  111.  *      combine name and label constants but will combine icon type
  112.  *      nodes.
  113.  */
  114. struct enode    **node;
  115. {       struct enode    *ep;
  116.         int             val, sc;
  117.         ep = *node;
  118.         if( ep == 0 )
  119.                 return;
  120.         switch( (*node)->nodetype ) {
  121.                 case en_b_ref:
  122.                 case en_w_ref:          /* optimize unary node */
  123.                 case en_l_ref:
  124.                 case en_cbw:
  125.                 case en_cbl:
  126.                 case en_cwl:
  127.                 case en_ainc:
  128.                 case en_adec:
  129.                 case en_not:
  130.                 case en_compl:
  131.                         opt0( &((*node)->v.p[0]));
  132.                         return;
  133.                 case en_uminus:
  134.                         opt0( &(ep->v.p[0]));
  135.                         if( ep->v.p[0]->nodetype == en_icon )
  136.                                 {
  137.                                 ep->nodetype = en_icon;
  138.                                 ep->v.i = -ep->v.p[0]->v.i;
  139.                                 }
  140.                         return;
  141.                 case en_add:
  142.                 case en_sub:
  143.                         opt0(&(ep->v.p[0]));
  144.                         opt0(&(ep->v.p[1]));
  145.                         if( ep->v.p[0]->nodetype == en_icon ) {
  146.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  147.                                         dooper(node);
  148.                                         return;
  149.                                         }
  150.                                 if( ep->v.p[0]->v.i == 0 ) {
  151.                     if( ep->nodetype == en_sub )
  152.                     {
  153.                         ep->v.p[0] = ep->v.p[1];
  154.                                             ep->nodetype = en_uminus;
  155.                     }
  156.                     else
  157.                         *node = ep->v.p[1];
  158.                                         return;
  159.                                         }
  160.                                 }
  161.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  162.                                 if( ep->v.p[1]->v.i == 0 ) {
  163.                                         *node = ep->v.p[0];
  164.                                         return;
  165.                                         }
  166.                                 }
  167.                         return;
  168.                 case en_mul:
  169.                         opt0(&(ep->v.p[0]));
  170.                         opt0(&(ep->v.p[1]));
  171.                         if( ep->v.p[0]->nodetype == en_icon ) {
  172.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  173.                                         dooper(node);
  174.                                         return;
  175.                                         }
  176.                                 val = ep->v.p[0]->v.i;
  177.                                 if( val == 0 ) {
  178.                                         *node = ep->v.p[0];
  179.                                         return;
  180.                                         }
  181.                                 if( val == 1 ) {
  182.                                         *node = ep->v.p[1];
  183.                                         return;
  184.                                         }
  185.                                 sc = pwrof2(val);
  186.                                 if( sc != -1 )
  187.                                         {
  188.                                         swap_nodes(ep);
  189.                                         ep->v.p[1]->v.i = sc;
  190.                                         ep->nodetype = en_lsh;
  191.                                         }
  192.                                 }
  193.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  194.                                 val = ep->v.p[1]->v.i;
  195.                                 if( val == 0 ) {
  196.                                         *node = ep->v.p[1];
  197.                                         return;
  198.                                         }
  199.                                 if( val == 1 ) {
  200.                                         *node = ep->v.p[0];
  201.                                         return;
  202.                                         }
  203.                                 sc = pwrof2(val);
  204.                                 if( sc != -1 )
  205.                                         {
  206.                                         ep->v.p[1]->v.i = sc;
  207.                                         ep->nodetype = en_lsh;
  208.                                         }
  209.                                 }
  210.                         break;
  211.                 case en_div:
  212.                         opt0(&(ep->v.p[0]));
  213.                         opt0(&(ep->v.p[1]));
  214.                         if( ep->v.p[0]->nodetype == en_icon ) {
  215.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  216.                                         dooper(node);
  217.                                         return;
  218.                                         }
  219.                                 if( ep->v.p[0]->v.i == 0 ) {    /* 0/x */
  220.                                         *node = ep->v.p[0];
  221.                                         return;
  222.                                         }
  223.                                 }
  224.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  225.                                 val = ep->v.p[1]->v.i;
  226.                                 if( val == 1 ) {        /* x/1 */
  227.                                         *node = ep->v.p[0];
  228.                                         return;
  229.                                         }
  230.                                 sc = pwrof2(val);
  231.                                 if( sc != -1 )
  232.                                         {
  233.                                         ep->v.p[1]->v.i = sc;
  234.                                         ep->nodetype = en_rsh;
  235.                                         }
  236.                                 }
  237.                         break;
  238.                 case en_mod:
  239.                         opt0(&(ep->v.p[0]));
  240.                         opt0(&(ep->v.p[1]));
  241.                         if( ep->v.p[1]->nodetype == en_icon )
  242.                                 {
  243.                                 if( ep->v.p[0]->nodetype == en_icon )
  244.                                         {
  245.                                         dooper(node);
  246.                                         return;
  247.                                         }
  248.                                 sc = pwrof2(ep->v.p[1]->v.i);
  249.                                 if( sc != -1 )
  250.                                         {
  251.                                         ep->v.p[1]->v.i = mod_mask(sc);
  252.                                         ep->nodetype = en_and;
  253.                                         }
  254.                                 }
  255.                         break;
  256.                 case en_and:    case en_or:
  257.                 case en_xor:    case en_rsh:
  258.                 case en_lsh:
  259.                         opt0(&(ep->v.p[0]));
  260.                         opt0(&(ep->v.p[1]));
  261.                         if( ep->v.p[0]->nodetype == en_icon &&
  262.                                 ep->v.p[1]->nodetype == en_icon )
  263.                                 dooper(node);
  264.                         break;
  265.                 case en_land:   case en_lor:
  266.                 case en_lt:        case en_le:
  267.                 case en_gt:        case en_ge:
  268.                 case en_eq:        case en_ne:
  269.                 case en_asand:  case en_asor:
  270.                 case en_asadd:  case en_assub:
  271.                 case en_asmul:  case en_asdiv:
  272.                 case en_asmod:  case en_asrsh:
  273.                 case en_aslsh:  case en_cond:
  274.                 case en_fcall:  case en_void:
  275.                 case en_assign:
  276.                         opt0(&(ep->v.p[0]));
  277.                         opt0(&(ep->v.p[1]));
  278.                         break;
  279.                 }
  280. }
  281.  
  282. int     xfold(node)
  283. /*
  284.  *      xfold will remove constant nodes and return the values to
  285.  *      the calling routines.
  286.  */
  287. struct enode    *node;
  288. {       int     i;
  289.         if( node == 0 )
  290.                 return 0;
  291.         switch( node->nodetype )
  292.                 {
  293.                 case en_icon:
  294.                         i = node->v.i;
  295.                         node->v.i = 0;
  296.                         return i;
  297.                 case en_add:
  298.                         return xfold(node->v.p[0]) + xfold(node->v.p[1]);
  299.                 case en_sub:
  300.                         return xfold(node->v.p[0]) - xfold(node->v.p[1]);
  301.                 case en_mul:
  302.                         if( node->v.p[0]->nodetype == en_icon )
  303.                                 return xfold(node->v.p[1]) * node->v.p[0]->v.i;
  304.                         else if( node->v.p[1]->nodetype == en_icon )
  305.                                 return xfold(node->v.p[0]) * node->v.p[1]->v.i;
  306.                         else return 0;
  307.                 case en_lsh:
  308.                         if( node->v.p[0]->nodetype == en_icon )
  309.                                 return xfold(node->v.p[1]) << node->v.p[0]->v.i;
  310.                          else if( node->v.p[1]->nodetype == en_icon )
  311.                                 return xfold(node->v.p[0]) << node->v.p[1]->v.i;
  312.                          else return 0;
  313.                 case en_uminus:
  314.                         return - xfold(node->v.p[0]);
  315.                 case en_rsh:    case en_div:
  316.                 case en_mod:    case en_asadd:
  317.                 case en_assub:  case en_asmul:
  318.                 case en_asdiv:  case en_asmod:
  319.                 case en_and:    case en_land:
  320.                 case en_or:     case en_lor:
  321.                 case en_xor:    case en_asand:
  322.                 case en_asor:   case en_void:
  323.                 case en_fcall:  case en_assign:
  324.                         fold_const(&node->v.p[0]);
  325.                         fold_const(&node->v.p[1]);
  326.                         return 0;
  327.                 case en_b_ref:  case en_w_ref:
  328.                 case en_l_ref:  case en_compl:
  329.                 case en_not:
  330.                         fold_const(&node->v.p[0]);
  331.                         return 0;
  332.                 }
  333.         return 0;
  334. }
  335.  
  336.  fold_const(node)
  337. /*
  338.  *      reorganize an expression for optimal constant grouping.
  339.  */
  340. struct enode    **node;
  341. {       struct enode    *ep;
  342.         int             i;
  343.         ep = *node;
  344.         if( ep == 0 )
  345.                 return;
  346.         if( ep->nodetype == en_add )
  347.                 {
  348.                 if( ep->v.p[0]->nodetype == en_icon )
  349.                         {
  350.                         ep->v.p[0]->v.i += xfold(ep->v.p[1]);
  351.                         return;
  352.                         }
  353.                 else if( ep->v.p[1]->nodetype == en_icon )
  354.                         {
  355.                         ep->v.p[1]->v.i += xfold(ep->v.p[0]);
  356.                         return;
  357.                         }
  358.                 }
  359.         else if( ep->nodetype == en_sub )
  360.                 {
  361.                 if( ep->v.p[0]->nodetype == en_icon )
  362.                         {
  363.                         ep->v.p[0]->v.i -= xfold(ep->v.p[1]);
  364.                         return;
  365.                         }
  366.                 else if( ep->v.p[1]->nodetype == en_icon )
  367.                         {
  368.                         ep->v.p[1]->v.i -= xfold(ep->v.p[0]);
  369.                         return;
  370.                         }
  371.                 }
  372.         i = xfold(ep);
  373.         if( i != 0 )
  374.                 {
  375.                 ep =(struct enode *) makenode(en_icon,(struct enode *)i,
  376.                                                       (struct enode *)0);
  377.                 ep =(struct enode *) makenode(en_add,ep,*node);
  378.                 *node = ep;
  379.                 }
  380. }
  381.  
  382.  opt4(node)
  383. /*
  384.  *      apply all constant optimizations.
  385.  */
  386. struct enode    **node;
  387. {
  388.         opt0(node);
  389.         fold_const(node);
  390.         opt0(node);
  391. }
  392.